package com.leetcode.Offer;

public class JZ13 {
    public int movingCount(int m, int n, int k) {
        //用于标识是否已经遍历过
        boolean[][] isVisit = new boolean[m][n];
        //从坐标0,0开始
        return moveSearch(m, n, isVisit, k, 0, 0);
    }

    private int moveSearch(int m, int n, boolean[][] isVisit, int k, int i, int j) {//i,j为当前位置
        if (i < 0 || j < 0 || i >= m || j >= n || isVisit[i][j] || (getDigitSum(i) + getDigitSum(j) > k)) {
            return 0;
        }
        isVisit[i][j] = true;
        return moveSearch(m, n, isVisit, k, i + 1, j)
                + moveSearch(m, n, isVisit, k, i - 1, j)
                + moveSearch(m, n, isVisit, k, i, j + 1)
                + moveSearch(m, n, isVisit, k, i, j - 1)
                + 1;

    }

    private int getDigitSum(int num) {//获得字数和
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new JZ13().getDigitSum(15));
        System.out.println(new JZ13().movingCount(38,15,9));
    }
}
